Bipartite weighted matching for on-line handwritten Chinese character recognition
Identifieur interne : 002A04 ( Main/Exploration ); précédent : 002A03; suivant : 002A05Bipartite weighted matching for on-line handwritten Chinese character recognition
Auteurs : Ai-Jia Hsieh [République populaire de Chine] ; Kuo-Chin Fan [République populaire de Chine] ; Tzu-I Fan [République populaire de Chine]Source :
- Pattern Recognition [ 0031-3203 ] ; 1994.
Abstract
The matching of line segments between input and prototype characters can be formulated as bipartite weighted matching problem. Under the assumption that the distance of the two line segments and the unmatched penalty of any line segment are given, the matching goal is to find a matching such that the sum of the weights of matching edges and the penalties of unmatched vertices is minimum. In this paper, the Hungarian method is applied to solve the matching problem by a reduction algorithm. Moreover, a greedy algorithm based on the Hungarian method is proposed by restricting the above matching which satisfies the constraints of geometric relation. For each iteration in the greedy algorithm, a matched pair is deleted if the relation of their neighbors does not match and a new matching is then found by applying Hungarian method. Finally, we can find a stable matching that preserves the geometric relation. We have implemented this method to recognize on-line Chinese handwritten characters permitting both stroke-order variation and stroke-number variation and a 91% recognition rate is attained.
Url:
DOI: 10.1016/0031-3203(94)00090-9
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000269
- to stream Istex, to step Curation: 000264
- to stream Istex, to step Checkpoint: 001D61
- to stream Main, to step Merge: 002B61
- to stream Main, to step Curation: 002A04
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Bipartite weighted matching for on-line handwritten Chinese character recognition</title><author><name sortKey="Hsieh, Ai Jia" sort="Hsieh, Ai Jia" uniqKey="Hsieh A" first="Ai-Jia" last="Hsieh">Ai-Jia Hsieh</name></author><author><name sortKey="Fan, Kuo Chin" sort="Fan, Kuo Chin" uniqKey="Fan K" first="Kuo-Chin" last="Fan">Kuo-Chin Fan</name></author><author><name sortKey="Fan, Tzu I" sort="Fan, Tzu I" uniqKey="Fan T" first="Tzu-I" last="Fan">Tzu-I Fan</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:D50D3E3513C50163F2839AC6218C5DBD334E92D7</idno><date when="1995" year="1995">1995</date><idno type="doi">10.1016/0031-3203(94)00090-9</idno><idno type="url">https://api.istex.fr/document/D50D3E3513C50163F2839AC6218C5DBD334E92D7/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000269</idno><idno type="wicri:Area/Istex/Curation">000264</idno><idno type="wicri:Area/Istex/Checkpoint">001D61</idno><idno type="wicri:doubleKey">0031-3203:1995:Hsieh A:bipartite:weighted:matching</idno><idno type="wicri:Area/Main/Merge">002B61</idno><idno type="wicri:Area/Main/Curation">002A04</idno><idno type="wicri:Area/Main/Exploration">002A04</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Bipartite weighted matching for on-line handwritten Chinese character recognition</title><author><name sortKey="Hsieh, Ai Jia" sort="Hsieh, Ai Jia" uniqKey="Hsieh A" first="Ai-Jia" last="Hsieh">Ai-Jia Hsieh</name><affiliation wicri:level="1"><country xml:lang="fr">République populaire de Chine</country><wicri:regionArea>Institute of Computer Science and Information Engineering, National Central University, Chungli, Taiwan 32054</wicri:regionArea><wicri:noRegion>Taiwan 32054</wicri:noRegion></affiliation><affiliation wicri:level="1"><country xml:lang="fr">République populaire de Chine</country><wicri:regionArea>Computer & Communication Research Laboratories, Industrial Technology Research Institute, Hsinchu, Taiwan 31015</wicri:regionArea><wicri:noRegion>Taiwan 31015</wicri:noRegion></affiliation></author><author><name sortKey="Fan, Kuo Chin" sort="Fan, Kuo Chin" uniqKey="Fan K" first="Kuo-Chin" last="Fan">Kuo-Chin Fan</name><affiliation><wicri:noCountry code="no comma">Author to whom all correspondence should be addressed.</wicri:noCountry></affiliation><affiliation wicri:level="1"><country xml:lang="fr">République populaire de Chine</country><wicri:regionArea>Institute of Computer Science and Information Engineering, National Central University, Chungli, Taiwan 32054</wicri:regionArea><wicri:noRegion>Taiwan 32054</wicri:noRegion></affiliation></author><author><name sortKey="Fan, Tzu I" sort="Fan, Tzu I" uniqKey="Fan T" first="Tzu-I" last="Fan">Tzu-I Fan</name><affiliation wicri:level="1"><country xml:lang="fr">République populaire de Chine</country><wicri:regionArea>Institute of Computer Science and Information Engineering, National Central University, Chungli, Taiwan 32054</wicri:regionArea><wicri:noRegion>Taiwan 32054</wicri:noRegion></affiliation></author></analytic><monogr></monogr><series><title level="j">Pattern Recognition</title><title level="j" type="abbrev">PR</title><idno type="ISSN">0031-3203</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1994">1994</date><biblScope unit="volume">28</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="143">143</biblScope><biblScope unit="page" to="151">151</biblScope></imprint><idno type="ISSN">0031-3203</idno></series><idno type="istex">D50D3E3513C50163F2839AC6218C5DBD334E92D7</idno><idno type="DOI">10.1016/0031-3203(94)00090-9</idno><idno type="PII">0031-3203(94)00090-9</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0031-3203</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The matching of line segments between input and prototype characters can be formulated as bipartite weighted matching problem. Under the assumption that the distance of the two line segments and the unmatched penalty of any line segment are given, the matching goal is to find a matching such that the sum of the weights of matching edges and the penalties of unmatched vertices is minimum. In this paper, the Hungarian method is applied to solve the matching problem by a reduction algorithm. Moreover, a greedy algorithm based on the Hungarian method is proposed by restricting the above matching which satisfies the constraints of geometric relation. For each iteration in the greedy algorithm, a matched pair is deleted if the relation of their neighbors does not match and a new matching is then found by applying Hungarian method. Finally, we can find a stable matching that preserves the geometric relation. We have implemented this method to recognize on-line Chinese handwritten characters permitting both stroke-order variation and stroke-number variation and a 91% recognition rate is attained.</div></front></TEI><affiliations><list><country><li>République populaire de Chine</li></country></list><tree><country name="République populaire de Chine"><noRegion><name sortKey="Hsieh, Ai Jia" sort="Hsieh, Ai Jia" uniqKey="Hsieh A" first="Ai-Jia" last="Hsieh">Ai-Jia Hsieh</name></noRegion><name sortKey="Fan, Kuo Chin" sort="Fan, Kuo Chin" uniqKey="Fan K" first="Kuo-Chin" last="Fan">Kuo-Chin Fan</name><name sortKey="Fan, Tzu I" sort="Fan, Tzu I" uniqKey="Fan T" first="Tzu-I" last="Fan">Tzu-I Fan</name><name sortKey="Hsieh, Ai Jia" sort="Hsieh, Ai Jia" uniqKey="Hsieh A" first="Ai-Jia" last="Hsieh">Ai-Jia Hsieh</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002A04 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002A04 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= OcrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:D50D3E3513C50163F2839AC6218C5DBD334E92D7
|texte= Bipartite weighted matching for on-line handwritten Chinese character recognition
}}
| This area was generated with Dilib version V0.6.32. |  |